package com.ruanruan.structure.graph.dfs;

import com.ruanruan.structure.graph.AdjList;
import com.ruanruan.structure.graph.Graph;

import java.util.Arrays;

/**
 * 二分图检测
 */
public class BiPartitionDetection {

    private Graph G;

    private boolean[] visited;

    private int[] colors;

    private boolean isBiPartition = true;

    public BiPartitionDetection(Graph G) {
        this.G = G;

        visited = new boolean[G.V()];
        colors = new int[G.V()];

        Arrays.fill(colors,-1);

        for (int i = 0; i < G.V(); i++) {
            if (!visited[i]) {
                if (!dfs(i,0)) {
                    break;
                }
            }
        }
    }

    private boolean dfs(int v, int color) {
        visited[v] = true;
        colors[v] = color;

        for (Integer w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w, 1 - color);
            }else if(colors[v] == colors[w]) {
                isBiPartition = false;
                return false;
            }
        }
        return true;
    }

    public boolean isBiPartition() {
        return isBiPartition;
    }

    public static void main(String[] args) {
        BiPartitionDetection detection = new BiPartitionDetection(new AdjList("resources/graph/g_bip.txt"));
        System.out.println(detection.isBiPartition());

        BiPartitionDetection detection2 = new BiPartitionDetection(new AdjList("resources/graph/g_cc.txt"));
        System.out.println(detection2.isBiPartition());
    }
}
